#ifndef DISJOINT_SET_H
#define DISJOINT_SET_H

#include <stdio.h>
#include <vector>

template<typename T>
void DeleteVector(T &v) {
  for (size_t i = 0; i < v.size(); ++i) {
    if (v[i] != NULL) {
      delete v[i];
      v[i] = NULL;
    }
  }
}

class DisjointSet {
public:
  struct ListSet;
  
  struct Node {
    Node() : next(NULL), set(NULL) { }
    Node *next;
    ListSet *set;
  };
  
  struct ListSet {
    ListSet() : head(NULL), tail(NULL), length(0) { }
  
    void Append(ListSet *set) {
      this->tail->next = set->head;
      this->tail = set->tail;
      this->length += set->length;
    }
    Node *head;
    Node *tail;
    int length;
  };

  DisjointSet(int n) : nodes_(n), sets_(n) { }

  ~DisjointSet() { 
    DeleteVector(nodes_);
    DeleteVector(sets_);
  }
  void MakeSet(int i) {
    nodes_[i] = new Node();
    sets_[i] = new ListSet();

    nodes_[i]->set = sets_[i];

    sets_[i]->head = nodes_[i];
    sets_[i]->tail = nodes_[i];
    sets_[i]->length = 1;
  }
  ListSet *Find(int i) {
    if (nodes_[i] == NULL) return NULL;
    return nodes_[i]->set;
  }
  void Union(int i, int j) {
    if (nodes_[i]->set->length > nodes_[j]->set->length) {
      this->Append(i, j);
    }
    else {
      this->Append(j, i);
    }
  }
private:
  void Append(int i, int j) {
    nodes_[i]->set->Append(nodes_[j]->set);
    for (Node *n = nodes_[j]->set->head; n != NULL; n = n->next) {
      n->set = nodes_[i]->set;
    }
  }
private:
  std::vector<Node*> nodes_;
  std::vector<ListSet*> sets_;
};

class DisjointSetForest {
public:
  struct Node {
    Node(int i) : parent(NULL), i(i), rank(0) { }
    Node *parent;
    int i;
    int rank;
  };
  DisjointSetForest(int n) : nodes_(n) { }

  ~DisjointSetForest() {
    DeleteVector(nodes_);
  }
  void MakeSet(int i) {
    nodes_[i] = new Node(i);
    nodes_[i]->parent = nodes_[i];
  }
  // root.parent == root;
  Node *Find(int i) {
    Node *inode = nodes_[i];
    if (inode->parent != inode)
      inode->parent = Find(inode->parent->i);
    return inode->parent;
  }
  void Union(int i, int j) {
    Node *iroot = Find(i);
    Node *jroot = Find(j);
    if (iroot == jroot) return;
    if (iroot->rank < jroot->rank) {
      iroot->parent = jroot;
    }
    else if (iroot->rank > jroot->rank) {
      jroot->parent = iroot;
    }
    else {
      iroot->parent = jroot;
      ++iroot->rank;
    }
  }
private:
  std::vector<Node*> nodes_;
};

#endif // DISJOINT_SET_H

